//https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked
//解法：非常好的题目！本题的难点在于如何去除重复解：先排序；控制双指针的移动；
//解法2：回溯法；最开始就要排好顺序！！！

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <set>
#include <numeric>

using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(nums.size()<3) return {};
        std::sort(nums.begin(),nums.end());
        vector<vector<int>>  res{};
        for(size_t i=0;i<nums.size()-2;++i){
            int a=nums[i];
            if(a>0) {
                return res;
            }
            if(i>0&& a==nums[i-1]){
                continue;
            }
            int j=i+1,k=nums.size()-1;
            while(j<k){
                int b=nums[j];
                int c=nums[k];
                int sum=a+b+c;
                if(sum==0){
                    res.push_back({a,b,c});
                    j++;
                    k--;
                    while(nums[j]==b && j<k){
                        ++j;
                    }
                    while(nums[k]==c && j<k){
                        k--;
                    }
                }else if(sum >0){
                    k--;
                }else {
                    j++;
                }
            }
        }     
        return res;   
    }
};


class Solution {
public:
    std::set<vector<int>> res;
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(nums.empty()) return {};
        vector<int> vec{};
        std::sort(nums.begin(),nums.end());
        dfs(nums,0,0,vec);
        vector<vector<int>> vec2(res.begin(),res.end());
        return vec2;
    }
    void dfs(vector<int>& nums,int one,int circule,std::vector<int>&vec){
        if(circule>=3){
            auto val = std::accumulate(vec.begin(),vec.end(),0);
            // for(auto item:vec){
            //     cout << item << ",";
            // }
            // cout << "---------"<<val << endl;
            if(val==0){
                std::vector<int> temp_vec(vec.begin(),vec.end());
                std::sort(temp_vec.begin(),temp_vec.end());
                res.insert(temp_vec);
                for(auto item:vec){
                    cout << item << ",";
                }
                cout << endl;
            }
            return;
        }
        for(size_t i=one;i<nums.size();++i){
            if(circule==0 && nums[i]>=0) {
                return;
            }
            vec.emplace_back(nums[i]);
            dfs(nums,i+1,circule+1,vec);
            vec.pop_back();
        }
    }
};